/**
 * 
 */
package No401_500.No451_460.FourSumII_454;

import java.util.HashMap;
import java.util.Map;

/** 
 * @author  作者 E-mail: ttljtw@qq.com
 * @date 创建时间：2017年3月4日 下午3:25:22 
 * @version 1.0 
 * @parameter  
 * @since  
 * @return  
 */
/**
 * @author 李敬
 *
 */
public class Solution {
	
	/*
	 * 将四数转变为两个部分，首先遍历AB的组合（任意两个都可以），存下他们组合后的和的情况，
	 * 然后遍历CD（另外两个）的和，看之前AB遍历的组合里有没有与此时值相反的值，
	 * 有的话就加上AB中这个相反数出现的次数。
	 * */
	
	public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
		if(A.length == 0){
			return 0;
		}
		Map<Integer, Integer> ab = new HashMap<Integer, Integer>();
		int ret = 0;
        for (int a : A) {
			for (int b : B) {
				int i = 0;
				if (ab.containsKey(a+b)) {
					i = ab.get(a+b);
				}
				ab.put(a+b, i+1);
			}
		}
        for (int c : C) {
			for (int d : D) {
				int i = 0;
				if (ab.containsKey(-(c+d))) {
					i = ab.get(-(c+d));
				}
				ret += i;
			}
		}
        return ret;
    }
	
	
	/*
	 * 自己完成，但会超时
	 * */
    static int ret;
    public int fourSumCount1(int[] A, int[] B, int[] C, int[] D) {
        ret = 0;
		cal(0, 0, A, B, C, D);
        return ret;
    }
    void cal(int count, int sum, int[] A, int[] B, int[] C, int[] D){
		if(count >= 4){
			if (sum == 0) {
				ret++;
				return;//返回链表
			}
			return;//返回空
		}
		else {
		    for(int i = 0;i<A.length;i++){
				switch (count) {
				case 0:
					cal(count + 1, sum + A[i], A, B, C, D);
					break;
				case 1:
					cal(count + 1, sum + B[i], A, B, C, D);
					break;
				case 2:
					cal(count + 1, sum + C[i], A, B, C, D);
					break;
				case 3:
					cal(count + 1, sum + D[i], A, B, C, D);
					break;
				}
		    }
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
